package unionFind

type UnionFind1 struct {
	// 路径压缩，现在u.Parent[x]不再表示x的父节点，而是表示x所在集合的代表元素
	Parent []int
}

func (u *UnionFind1) init(n int) {
	u.Parent = make([]int, n)
	for i := 0; i < n; i++ {
		u.Parent[i] = i
	}
}

// 查找元素x所在集合的代表元素
// 路径压缩，现在u.Parent[x]不再表示x的父节点，而是表示x所在集合的代表元素
func (u *UnionFind1) Find(x int) int {
	if x == u.Parent[x] {
		return x
	}
	u.Parent[x] = u.Find(u.Parent[x])
	return u.Parent[x]
}

// 判断元素i,j是否在同一个集合中
func (u *UnionFind1) IsConnected(i, j int) bool {
	return u.Find(i) == u.Find(j)
}

// 将节点i所在集合的代表元素的父元素设置为集合j所在元素的代表元素
// 即将i所在集合合并到j所在集合
func (u *UnionFind1) Merger(i, j int) {
	u.Parent[u.Find(i)] = u.Find(j)
}
